package 中等.贪心思想;

import javafx.util.Pair;

import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 * 如果字符串中不含有任何 'aaa'，'bbb' 或 'ccc' 这样的字符串作为子串，那么该字符串就是一个「快乐字符串」。
 * <p>
 * 给你三个整数 a，b ，c，请你返回 任意一个 满足下列全部条件的字符串 s：
 * <p>
 * s 是一个尽可能长的快乐字符串。
 * s 中 最多 有a 个字母 'a'、b 个字母 'b'、c 个字母 'c' 。
 * s 中只含有 'a'、'b' 、'c' 三种字母。
 * 如果不存在这样的字符串 s ，请返回一个空字符串 ""。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/longest-happy-string
 */
public class 最长快乐字符串_1405 {

    public static void main(String[] args) {

        System.out.println(efficientLongestDiverseString(1, 1, 7));

    }

    /**
     * 贪心：
     * 每次优先选择a,b,c中数量最多的字母
     * 如果最多的字母大于2，连续选两次该字母
     * 注意：
     * 将要构成aaa,bbb,ccc,则不选最多的字母，选1个第二多的字母
     * 为什么第二多的字母选1个？ 例如aabbaa,aabaabaa，2121是最优解
     * 使用优先队列来取最多字母和第二多字母
     *
     * @param a
     * @param b
     * @param c
     * @return
     */
    public static String longestDiverseString(int a, int b, int c) {
        StringBuilder stringBuilder = new StringBuilder();
        Queue<Pair<Character, Integer>> priorityQueue = new PriorityQueue<>(3, (o1, o2) -> (o2.getValue()) - o1.getValue());
        priorityQueue.offer(new Pair<>('a', a));
        priorityQueue.offer(new Pair<>('b', b));
        priorityQueue.offer(new Pair<>('c', c));

        while (priorityQueue.peek().getValue() > 0) {
            Pair pair1;
            Pair pair2;
            Pair<Character, Integer> maxNum = priorityQueue.poll();
            if (maxNum.getValue() > 2) {
                if (stringBuilder.length() > 0 && stringBuilder.charAt(stringBuilder.length() - 1) == maxNum.getKey()) {
                    pair1 = maxNum;
                } else {
                    pair1 = new Pair(maxNum.getKey(), maxNum.getValue() - 2);
                    stringBuilder.append(maxNum.getKey());
                    stringBuilder.append(maxNum.getKey());
                }
            } else {
                if (stringBuilder.length() > 1 && stringBuilder.charAt(stringBuilder.length() - 1) == maxNum.getKey() && stringBuilder.charAt(stringBuilder.length() - 2) == maxNum.getKey()) {
                    pair1 = maxNum;
                } else {
                    pair1 = new Pair(maxNum.getKey(), maxNum.getValue() - 1);
                    stringBuilder.append(maxNum.getKey());
                }
            }

            if (priorityQueue.peek().getValue() > 0) {
                Pair<Character, Integer> secondNum = priorityQueue.poll();
                pair2 = new Pair(secondNum.getKey(), secondNum.getValue() - 1);
                stringBuilder.append(secondNum.getKey());
            } else {
                return stringBuilder.toString();
            }
            priorityQueue.offer(pair1);
            priorityQueue.offer(pair2);
        }
        return stringBuilder.toString();
    }

    /**
     * 代码优化
     * 尽量长的快乐字符串，如果可能剩下字母，那么那个字母必然是最多的那个
     * 每次选择一个最多字母的字母，需要判断和前面两个字母是否相同
     * 如果相同，则选择第二多的一个字母
     *
     * @param a
     * @param b
     * @param c
     * @return
     */
    public static String longestDiverseString2(int a, int b, int c) {
        StringBuilder stringBuilder = new StringBuilder();
        Queue<Pair<Character, Integer>> priorityQueue = new PriorityQueue<>(3, (o1, o2) -> o2.getValue() - o1.getValue());
        priorityQueue.offer(new Pair<>('a', a));
        priorityQueue.offer(new Pair<>('b', b));
        priorityQueue.offer(new Pair<>('c', c));
        while (priorityQueue.peek().getValue() > 0) {  //最大的数要大于0
            int curLen = stringBuilder.length();
            Pair<Character, Integer> curOne = priorityQueue.poll();
            if (curLen > 1 && curOne.getKey() == stringBuilder.charAt(curLen - 1) && curOne.getKey() == stringBuilder.charAt(curLen - 2)) {
                if (priorityQueue.peek().getValue() > 0) {  //第二大字母要大于0
                    Pair<Character, Integer> curTwo = priorityQueue.poll();
                    stringBuilder.append(curTwo.getKey());
                    priorityQueue.offer(new Pair<>(curTwo.getKey(), curTwo.getValue() - 1));
                } else {
                    return stringBuilder.toString();
                }
            }
            stringBuilder.append(curOne.getKey());  //第二大的字母-1，最大字母仍然是最大
            priorityQueue.offer(new Pair<>(curOne.getKey(), curOne.getValue() - 1));
        }
        return stringBuilder.toString();
    }

    /**
     * 优先队列时间复杂度：
     * PriorityQueue的peek()和element操作是常数时间，add(), offer(), 无参数的remove()以及poll()方法的时间复杂度都是log(N)
     * 直接采用数组进行排序
     *
     * @param a
     * @param b
     * @param c
     * @return
     */
    public static String efficientLongestDiverseString(int a, int b, int c) {
        StringBuilder stringBuilder = new StringBuilder();
        pair[] pairs = new pair[]{new pair('a', a), new pair('b', b), new pair('c', c)};
        Arrays.sort(pairs, (o1, o2) -> o2.value - o1.value);
        while (pairs[0].value > 0) {
            pair curOne = pairs[0];
            int curLen = stringBuilder.length();
            if (curLen > 1 && curOne.key == stringBuilder.charAt(curLen - 1) && curOne.key == stringBuilder.charAt(curLen - 2)) {
                if (pairs[1].value > 0) {  //第二大字母要大于0
                    pair curTwo = pairs[1];
                    stringBuilder.append(curTwo.key);
                    curTwo.value--;
                } else {
                    return stringBuilder.toString();
                }
            }
            stringBuilder.append(curOne.key);
            curOne.value--;
            Arrays.sort(pairs, (o1, o2) -> o2.value - o1.value);
        }
        return stringBuilder.toString();
    }

    static class pair {

        private Character key;

        private Integer value;

        public pair(Character key, Integer value) {
            this.key = key;
            this.value = value;
        }
    }

}
